#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	return 0;
}


//  有效三角形的个数  
class Solution
{
public:
    int triangleNumber(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
        int ret = 0, n = nums.size();
        for (int i = n - 1; i >= 2; i--)
        {
            int left = 0, right = i - 1;
            while (left < right)
            {
                if (nums[left] + nums[right] > nums[i])
                {
                    ret += right - left;
                    right--;
                }
                else
                {
                    left++;
                }
            }
        }
        return ret;
    }
};


//  和为s的两个数字
class Solution
{
public:
    vector<int> twoSum(vector<int>& price, int target)
    {
        int left = 0, right = price.size() - 1;
        while (left < right)
        {
            int sum = price[left] + price[right];
            if (sum == target)
                return { price[left],price[right] };
            else if (sum > target)
                right--;
            else
                left++;
        }
        return { -1,-1 };
    }
};

//  三数之和  
class Solution
{
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        vector<vector<int>> ret;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n; )
        {
            if (nums[i] > 0) break;
            int left = i + 1, right = n - 1, target = -nums[i];
            while (left < right)
            {
                int sum = nums[left] + nums[right];
                if (sum > target)
                    right--;
                else if (sum < target)
                    left++;
                else
                {
                    ret.push_back({ nums[i], nums[left], nums[right] });
                    left++, right--;
                    while (left < right && nums[left - 1] == nums[left]) left++;
                    while (left < right && nums[right + 1] == nums[left]) right--;
                }
            }
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
};

//  四数之和
class Solution
{
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target)
    {
        int n = nums.size();
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n; )
        {
            for (int j = i + 1; j < n; )
            {
                int left = j + 1, right = n - 1;
                long long aim = (long long)target - nums[i] - nums[j];
                while (left < right)
                {
                    int sum = nums[left] + nums[right];
                    if (sum < aim) left++;
                    else if (sum > aim)right--;
                    else
                    {
                        ret.push_back({ nums[i], nums[j], nums[left], nums[right] });
                        left++, right--;
                        while (left < right && nums[left - 1] == nums[left]) left++;
                        while (left < right && nums[right + 1] == nums[right]) right--;
                    }
                }
                j++;
                while (j < n && nums[j] == nums[j - 1]) j++;
            }
            i++;
            while (i < n && nums[i] == nums[i - 1])i++;
        }
        return ret;
    }
};              

class Solution    //  希尔排序
{
public:

    void ShellSort(vector<int>& arr, int n)
    {
        int gap = n;
        while (gap > 1)
        {
            gap = gap / 3 + 1;
            for (int i = 0; i < n - gap; i++)
            {
                int end = i;
                int tmp = arr[end + gap];
                while (end >= 0)
                {
                    if (arr[end] > tmp)
                    {
                        arr[end + gap] = arr[end];
                        end -= gap;
                    }
                    else
                        break;
                }
                arr[end + gap] = tmp;
            }
        }

    }
    int findKthLargest(vector<int>& nums, int k)
    {
        int n = nums.size();
        ShellSort(nums, n);
        int ret = 0;
        for (int i = n - 1; i >= 0; i--)
        {
            k--;
            if (k == 0)
            {
                ret = nums[i];
                break;
            }
        }
        return ret;
    }
};



//  归并排序
class Solution
{
public:
    void mergeSort(vector<int>& nums, int left, int right)
    {
        if (left >= right)
            return;
        int mid = (right + left) >> 1;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        int* cur = new int[right - left + 1];
        int cur1 = left, cur2 = mid + 1, index = 0;
        while (cur1 <= mid && cur2 <= right)
        {
            cur[index++] = nums[cur1] > nums[cur2] ? nums[cur2++] : nums[cur1++];
        }
        while (cur1 <= mid)
            cur[index++] = nums[cur1++];
        while (cur2 <= right)
            cur[index++] = nums[cur2++];
        for (int i = left; i <= right; i++)
        {
            nums[i] = cur[i - left];
        }
        delete[]cur;
    }
    vector<int> sortArray(vector<int>& nums)
    {
        int n = nums.size();
        mergeSort(nums, 0, n - 1);
        return nums;
    }
};





// 被围绕的区域
// 本题正着去遍历去递归是比较难处理的
// 可以对四条边进行dfs深搜  把搜到的海洋都标记起来
//  剩下的就是 被围绕的区域
class Solution
{
    int dx[4] = { 1, -1, 0, 0 };
    int dy[4] = { 0, 0, 1, -1 };
    int n, m;
    bool vis[201][201];
public:
    void solve(vector<vector<char>>& board)
    {
        n = board.size(), m = board[0].size();
        for (int i = 0; i < n; i++)    //  遍历四条边的  o
        {
            if (board[i][0] == 'O') dfs(board, i, 0);
            if (board[i][m - 1] == 'O') dfs(board, i, m - 1);
        }
        for (int i = 0; i < m; i++)
        {
            if (board[0][i] == 'O') dfs(board, 0, i);
            if (board[n - 1][i] == 'O') dfs(board, n - 1, i);
        }

        for (int i = 1; i < n - 1; i++)  //  最后更新结果  把未标记的 o 改为 x
        {
            for (int j = 1; j < m - 1; j++)
            {
                if (board[i][j] == 'O' && !vis[i][j])
                {
                    board[i][j] = 'X';
                }
            }
        }
    }
    void dfs(vector<vector<char>>& board, int i, int j)
    {
        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k];
            int y = j + dy[k];
            if (x < n && x >= 0 && y < m && y >= 0 && board[x][y] == 'O' && !vis[x][y]) // 递归条件
            {
                vis[x][y] = 1;  // 满足条件就标记  
                dfs(board, x, y);
            }
        }
    }
};

//  bfs解法
//  还是相同的思路  和前面几个题目都类似的
class Solution
{
    int dx[4] = { 1, -1, 0, 0 };
    int dy[4] = { 0, 0, 1, -1 };
    int n, m;
    bool vis[201][201];
public:
    void solve(vector<vector<char>>& board)
    {
        n = board.size(), m = board[0].size();
        for (int i = 0; i < n; i++)   // 正常遍历四条边  进行bfs搜索
        {
            if (board[i][0] == 'O') bfs(board, i, 0);
            if (board[i][m - 1] == 'O') bfs(board, i, m - 1);
        }
        for (int i = 0; i < m; i++)
        {
            if (board[0][i] == 'O') bfs(board, 0, i);
            if (board[n - 1][i] == 'O') bfs(board, n - 1, i);
        }

        for (int i = 1; i < n - 1; i++)
        {
            for (int j = 1; j < m - 1; j++)
            {
                if (board[i][j] == 'O' && !vis[i][j])
                {
                    board[i][j] = 'X';
                }
            }
        }
    }
    void bfs(vector<vector<char>>& board, int i, int j)
    {
        vis[i][j] = 1;
        queue<pair<int, int>> q;
        q.push({ i, j });
        while (q.size())
        {
            i = q.front().first, j = q.front().second;
            q.pop();
            for (int k = 0; k < 4; k++)
            {
                int x = i + dx[k];
                int y = j + dy[k];
                if (x < n && x >= 0 && y < m && y >= 0 && board[x][y] == 'O' && !vis[x][y])  // 判断条件
                {
                    vis[x][y] = 1;   // 满足条件 标记 
                    q.push({ x, y }); // 入队列
                }
            }

        }
    }
};